//============================================================================
// Name        : QuadMagico.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int ** algoritmoSiames(const int tamanho) {
	const int meio = tamanho/2;
	int ** quadMagico = new int * [tamanho];
		for (int i = 0; i<tamanho; i++)
			quadMagico[i] = new int[tamanho];

	for (int i = 0; i< tamanho; i++){ 
		for (int j = meio; j< tamanho+meio; j++){
			cout << endl;
			quadMagico[ (2*tamanho-j+meio-i)%tamanho ] [ (tamanho+j-i)%tamanho ] = tamanho*i + j-meio+1;
		}
	}
	return quadMagico;
}

bool isSpecial (int i, int j) {
	if (i%4 == j%4)
		return true;
	if (i%4 + j%4 == 3)
		return true;
	return false;
}

int ** algoritmoX(const int tamanho) {
	int ** quadMagico = new int *[tamanho];
	for (int i = 0; i<tamanho; i++)
		quadMagico[i] = new int[tamanho];
	
	for (int i = 0; i< tamanho; i++)
		for (int j = 0; j<tamanho; j++) {
			if ( isSpecial(i, j) )
				quadMagico[i][j] = (tamanho*tamanho + 1) - tamanho*i - j - 1;
			else
				quadMagico[i][j] = tamanho*i + j + 1;
		}
	return quadMagico;
}

int ** montaMatrizGuia( int tamanho) {
	enum {L,U,X};
	int m = (tamanho - 2) / 4;
	int ** matrizGuia = new int * [tamanho/2];
	for (int i = 0; i<tamanho/2; i++)
		matrizGuia[i] = new int[tamanho/2];
	
	for (int i = 0; i< tamanho/2; i++)
		for (int j = 0; j < tamanho/2; j++)
		{
			if (i <= m)
				matrizGuia[i][j] = L;
			else if (i == m+1)
				matrizGuia[i][j] = U;
			else
				matrizGuia[i][j] = X;
		}
	matrizGuia[m+1][m] = L;
	matrizGuia[m][m] = U;
	
	return matrizGuia;
}

void atualizaQuadMagico(int i, int j, int** quadMagico, int** matrizGuia, int valorBase) {
	enum {L,U,X};
	int rRef = 2*i;
	int cRef = 2*j;
	
	//cout << rRef << " " << cRef << " " << valorBase << endl; 
	//cout << cRef << " " << rRef << endl << endl;
	
	switch (matrizGuia[i][j]){
	case L:
		quadMagico[rRef][cRef+1] = 4*valorBase + 1;
		quadMagico[rRef+1][cRef] = 4*valorBase + 2;
		quadMagico[rRef+1][cRef+1] = 4*valorBase + 3;
		quadMagico[rRef][cRef] = 4*valorBase + 4;
		break;
	case U:
		quadMagico[rRef][cRef] = 4*valorBase+ 1;
		quadMagico[rRef+1][cRef] = 4*valorBase + 2;
		quadMagico[rRef+1][cRef+1] = 4*valorBase + 3;
		quadMagico[rRef][cRef+1] = 4*valorBase + 4;
		break;
	case X:
		quadMagico[rRef][cRef] = 4*valorBase+ 1;
		quadMagico[rRef+1][cRef+1] = 4*valorBase + 2;
		quadMagico[rRef+1][cRef] = 4*valorBase + 3;
		quadMagico[rRef][cRef+1] = 4*valorBase + 4;
		break;
	}
}

int ** algoritmoLUX (const int tamanho) {
	const int meio = tamanho/2;
	const int quarto = meio/2;
	int ** quadMagico = new int *[tamanho];
	for (int i = 0; i<tamanho; i++)
		quadMagico[i] = new int[tamanho];
	
	int ** matrizGuia = montaMatrizGuia(tamanho);	
	for (int i = 0; i< meio; i++){ 
			for (int j = quarto; j< meio+quarto; j++){
				atualizaQuadMagico((2*meio-j+quarto-i)%meio,  (meio+j-i)%meio, quadMagico, matrizGuia, meio*i + j-quarto);
			}
		}
	return quadMagico;
}



int ** resolveQuadrado (const int tamanho) {
	int ** quadMagico;
	if (tamanho%2 == 1)
		quadMagico = algoritmoSiames(tamanho);
	else if (tamanho%4 == 0)
		quadMagico = algoritmoX(tamanho);
	else
		quadMagico = algoritmoLUX(tamanho);
	return quadMagico;
}

char * digitSpaces(int numero) {
	int numEspacos = 1;
	while (numero = numero/10 > 0)
		numEspacos ++;
	char * espacos = new char[numEspacos];
	for (int i = 0; i < numEspacos; i++)
		espacos[i] = ' ';
	return espacos;
}

int main() {
	int tamanho;
	int ** quadMagico;
	cout << "Digite o tamanho do quadrado magico desejado: " << endl; 
	cin >> tamanho;
	if (tamanho > 100)
		cout << "Tamanho muito grande. Programa preguicoso irah terminar" << endl;
	else {
		quadMagico = resolveQuadrado(tamanho);
	}
	cout << "MC suga!!!" << endl; 
	cout << endl;
	char * espacos = digitSpaces(tamanho*tamanho);
	for (int i =0; i< tamanho; i++){
		for (int j = 0; j< tamanho; j++) {
			cout << quadMagico[i][j];
			cout << espacos;
		}
		cout << endl; 
	}
	
	for (int i = 0; i< tamanho; i++) {
		delete [] quadMagico[i];
	}
	delete [] quadMagico;
	return 0;
}
